package com.xiyou.week01.linked;

/**
 * 142. 环形链表 II
 *
 * @ClassName：LeetCode142
 * @Author：西柚
 * @Date：2021/11/20 4:17 下午
 * @Versiion：1.0
 */
public class HasCycle2 {

    /**
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：返回索引为 1 的链表节点
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     *
     * @param head
     * @return
     */
    public ListNode hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next; // 快指针，一次移动两步
            slow = slow.next;       // 慢指针，一次移动一步
            if (fast == slow) {     // 快慢指针相遇，表明有环
                while (head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode nodeSta = new ListNode(3);    //创建首节点
        ListNode nextNode;                     //声明一个变量用来在移动过程中指向当前节点
        nextNode = nodeSta;                      //指向首节点

        //创建链表
        ListNode node = new ListNode(2);  //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

        node = new ListNode(0);         //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

        node = new ListNode(-4);        //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

        nextNode = nodeSta;                   //重新赋值让它指向首节点
        print(nextNode);                      //打印输出

        HasCycle2 leetCode142 = new HasCycle2();
        System.out.println(leetCode142.hasCycle(nodeSta));

    }

    //打印输出方法
    static void print(ListNode listNoed) {
        //创建链表节点
        while (listNoed != null) {
            System.out.println("节点:" + listNoed.val);
            listNoed = listNoed.next;
        }
        System.out.println();
    }

}
